#pragma once
#include<iostream>
using namespace std;


// K模型
template<class K>
struct BSTNode
{
	K _key;
	BSTNode<K>* _left;
	BSTNode<K>* _right;

	BSTNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

template<class K>
class BSTree
{
	typedef BSTNode<K> Node;
public:
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

	bool Insert(const K& key)
	{
		// 1.树为空
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		// 2.树不为空
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		// 找到位置，进行插入
		cur = new Node(key);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}

	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else // 找到节点进行删除
			{
				// 0-1 个孩子的情况
				if (cur->_left == nullptr)//被删除节点的左为空
				{
					if (parent == nullptr)
					{
						_root = cur->_right;
					}
					else 
					{
						if (parent->_left == cur)
							parent->_left = cur->_right;
						else // parent->_right == cur
							parent->_right = cur->_right;
					}
					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)// 被删除节点的右为空
				{
					if (parent == nullptr)
						_root = cur->_left;
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_left;
						else // parent->_right == cur
							parent->_right = cur->_left;
					}
					delete cur;
					return true;
				}
				else // 删除两个孩子的情况
				{
					// 找要删除节点的右子树的最小节点作为替代节点
					Node* rightMinP = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinP = rightMin;
						rightMin = rightMin->_left;//一直往被删除节点右子树中的最小节点找
					}
					// 找到右子树中最小的值
					cur->_key = rightMin->_key;//代替要删除的节点
					//rightMin不一定是rightMinP的左，也有可能是右（rightMinP = cur）
					if (rightMinP->_left == rightMin)
						rightMinP->_left = rightMin->_right;
					else
						rightMinP->_right = rightMin->_right;

					delete cur;
					return true;
				}
			}
		}
		return false;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root << " ";
		_InOrder(root->_right);
	}

	Node* _root = nullptr;
};

// KV模型
namespace KeyValue
{
	template<class K,class V>
	struct BSTNode
	{
		K _key;
		V _value;
		BSTNode<K, V>* _left;
		BSTNode<K, V>* _right;

		BSTNode(const K& key, const V& value)
			:_key(key)
			,_value(value)
			,_left(nullptr)
			,_right(nullptr)
		{}
	};

	template<class K,class V>
	class BSTree
	{
		typedef BSTNode<K, V> Node;
	public:
		BSTree()
			:_root(nullptr)
		{}

		Node* Find(const K& key)// 返回节点指针
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else //找到
				{
					return cur;//返回节点指针
				}
			}
			return nullptr;
		}

		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else //找到相同数值，不能插入
				{
					return false;
				}
			}
			// 找到要插入的位置
			cur = new Node(key, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			return true;
		}

		bool Erase(const K& key)
		{
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else //找到
				{
					// 删除的节点有 0-1 个孩子
					if (cur->_left == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
						delete cur;
						return true;
					}
					else if (cur->_right == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
						delete cur;
						return true;
					}
					else// 删除的节点有 2 个孩子
					{
						Node* rightMinP = nullptr;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinP = rightMin;
							rightMin = rightMin->_left;
						}
						cur->_key = rightMin->_key;

						if (rightMinP->_left == rightMin)
							rightMinP->_left = rightMin->_right;
						else
							rightMinP->_right = rightMin->_right;

						delete rightMin;
						return true;;
					}
				}
			}
			return false;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr) return;
			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;;
			_InOrder(root->_right);
		}

		Node* _root = nullptr;
	};
}